`
https://leetcode.cn/problems/minimize-maximum-component-cost/
`

/**
 * @param {number} n
 * @param {number[][]} edges
 * @param {number} k
 * @return {number}
 */
var minCost = function (n, edges, k) {
  if (n === k) return 0

  edges.sort((a, b) => a[2] - b[2])
  const uf = new UnionFind(n)
  for (const [u, v, w] of edges) {
    uf.connect(u, v)
    if (uf.count() === k) {
      // 首次合并到 k 个连通块，当前合并的边权肯定是所有结果里最大边权的最小值
      return w
    }
  }
};

class UnionFind {
  constructor(n) {
    this._count = n
    this.parent = Array.from({ length: n }, (_, index) => index)
    this.size = new Array(n).fill(1)
  }
  // 将节点 p 和节点 q 连通
  connect(p, q) {
    const rootP = this.find(p)
    const rootQ = this.find(q)

    if (rootP === rootQ) {
      return false
    }

    if (this.size[rootP] < this.size[rootQ]) {
      this.parent[rootP] = rootQ
      this.size[rootQ] += this.size[rootP]
    } else {
      this.parent[rootQ] = rootP
      this.size[rootP] += this.size[rootQ]
    }
    this._count--
    return true
  }

  isConnected(p, q) {
    const rootP = this.find(p)
    const rootQ = this.find(q)
    return rootP === rootQ
  }

  count() {
    return this._count
  }

  componentSizeOf(x) {
    const rootX = this.find(x)
    return this.size[rootX]
  }

  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x])
    }
    return this.parent[x]
  }
}